package com.leetcode.algorithm.y18.m05;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * leetcode-cn.com
 * 405. 数字转换为十六进制数
 * 409. 最长回文串
 * 412. Fizz Buzz
 * 414. 第三大的数
 * 448. 找到所有数组中消失的数字
 * 453. 最小移动次数使数组元素相等
 * 784. 字母大小写全排列
 * 788. 旋转数字
 * 796. 旋转字符串
 * @author: jie.deng
 * @time: 2018年5月21日 上午10:24:22
 */
public class MySolution0521 {
	/**
	 * 409. 最长回文串
	 * 给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
	 * 在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
	 * 注意: 
	 * 假设字符串的长度不会超过 1010。
	 * 
	 * 示例 1:
	 * 输入: "abccccdd"
	 * 输出: 7
	 * 解释: 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
	 * 
	 * @param s
	 * @return
	 */
	public int longestPalindrome(String s) {
		Map<Character, Integer> map = new HashMap<Character, Integer>();
		char[] chars = s.toCharArray();
		for (int i = 0; i < chars.length; i++) {
			Integer count = map.get(chars[i]);
			map.put(chars[i], count == null ? 1 : count + 1);
		}
		boolean oddFlag = false;
		int sum = 0;
		Set<Character> entrys = map.keySet();
		for (Iterator<Character> iterator = entrys.iterator(); iterator.hasNext();) {
			Character ch = (Character) iterator.next();
			int i = map.get(ch);
			if (i == 1) {
				oddFlag = true;
			} else {
				sum += (i - i % 2);
				if (!oddFlag && i % 2 == 1) {
					oddFlag = true;
				}
			}
		}
		return sum + (oddFlag ? 1 : 0);
	}
    
    /**
	 * 412. Fizz Buzz
	 * 
	 * 写一个程序，输出从 1 到 n 数字的字符串表示。
	 * 1. 如果 n 是3的倍数，输出“Fizz”；
	 * 2. 如果 n 是5的倍数，输出“Buzz”；
	 * 3.如果 n 同时是3和5的倍数，输出 “FizzBuzz”。
	 * 
	 * @param n
	 * @return
	 */
	public List<String> fizzBuzz(int n) {
		List<String> list = new ArrayList<String>(n);
		for (int i = 0; i < n; i++) {
			list.add("" + (i + 1));
		}
		for (int i = 2; i < n; i = i + 3) {
			list.set(i, "Fizz");
		}
		for (int i = 4; i < n; i = i + 5) {
			list.set(i, "Buzz");
		}
		for (int i = 14; i < n; i = i + 15) {
			list.set(i, "FizzBuzz");
		}
		return list;
	}
	
	/**
	 * 414. 第三大的数
	 * 给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
	 * 
	 * 示例 1:
	 * 输入: [3, 2, 1]
	 * 输出: 1
	 * 解释: 第三大的数是 1. 
	 * 
	 * 示例 2:
	 * 输入: [1, 2]
	 * 输出: 2
	 * 解释: 第三大的数不存在, 所以返回最大的数 2 . 
	 * 
	 * 示例 3:
	 * 输入: [2, 2, 3, 1]
	 * 输出: 1
	 * 解释: 注意，要求返回第三大的数，是指第三大且唯一出现的数。 存在两个值为2的数，它们都排第二。
	 * 
	 * @param nums
	 * @return
	 */
	public int thirdMax(int[] nums) {
		int i1 = nums[0];
		int i2 = Integer.MIN_VALUE;
		int i3 = Integer.MIN_VALUE;
		int count = 1;
		for (int i = 1; i < nums.length; i++) {
			if (nums[i] > i1) {
				if (count < 3) {
					count++;
				}
				i3 = i2;
				i2 = i1;
				i1 = nums[i];
			} else if (nums[i] == i1) {
				continue;
			} else if (nums[i] > i2) {
				if (count < 3) {
					count++;
				}
				i3 = i2;
				i2 = nums[i];
			} else if (nums[i] == i2) {
				if (count == 1) {	//注意
					count++;
				}				
				continue;
			} else if (nums[i] > i3) {
				if (count < 3) {
					count++;
				}
				i3 = nums[i];
			} else if (nums[i] == i3) {
				if (count < 3) {
					count++;
				}
			}
		}
		if (count == 3) {
			return i3;
		}
		return i1;
	}
	
	/**
	 * 405. 数字转换为十六进制数
	 * 给定一个整数，编写一个算法将这个数转换为十六进制数。对于负整数，我们通常使用 补码运算 方法。
	 * 
	 * 注意:
	 * 十六进制中所有字母(a-f)都必须是小写。
	 * 十六进制字符串中不能包含多余的前导零。如果要转化的数为0，那么以单个字符'0'来表示；对于其他情况，十六进制字符串中的第一个字符将不会是0字符。
	 * 给定的数确保在32位有符号整数范围内。 
	 * 不能使用任何由库提供的将数字直接转换或格式化为十六进制的方法。 
	 * 
	 * 示例 1：
	 * 输入: 26
	 * 输出: "1a" 
	 * 
	 * 示例 2：
	 * 输入: -1
	 * 输出: "ffffffff"
	 * 
	 * @param num
	 * @return
	 */
	public String toHexSolution(int num) {
		if (num == 0) {
			return "0";
		}
		char[] chars = new char[] { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };
		StringBuffer sb = new StringBuffer();
		while (num != 0) {
			sb.append(chars[num & 0xf]);	// num & 0xf 获取二进制表示的后4位
			num >>>= 4;
		}
		return sb.reverse().toString();
	}	
	public String toHex(int num) {
		boolean negFlag = false;
		if (num < 0) {
			if (num == Integer.MIN_VALUE) {
				return "80000000";
			}
			negFlag = true;
			num = -num;
		}
		StringBuffer sb = new StringBuffer();
		int i = num % 16;
		if (i >= 10) {
			sb.append((char) (i - 10 + 'a'));
		} else {
			sb.append(i);
		}
		while (num / 16 > 0) {
			num /= 16;
			i = num % 16;
			if (i >= 10) {
				sb.append((char) (i - 10 + 'a'));
			} else {
				sb.append(i);
			}
		}
		if (!negFlag) {
			return sb.reverse().toString();
		}
		// 求反码
		char[] chars = sb.reverse().toString().toCharArray();
		int len = chars.length;
		char[] charArr = new char[8];
		for (i = 0; i < 8; i++) {
			if (len + i < 8) {
				charArr[i] = 'f';
			} else {
				if (chars[i + len - 8] >= 'a' && chars[i + len - 8] <= 'f') {
					charArr[i] = (char) ('f' - chars[i + len - 8] + '0');
				} else if (chars[i + len - 8] >= '0' && chars[i + len - 8] <= '9') {
					if (chars[i + len - 8] - '0' < 6) {
						charArr[i] = (char) ('f' - (chars[i + len - 8] - '0'));
					} else {
						charArr[i] = (char) ('9' - (chars[i + len - 8] - '0' - 6));
					}
				}
			}
		}
		// 末位加1
		for (i = 7; i > 0; i--) {
			if (charArr[i] == 'f') {
				charArr[i] = '0';
			} else {
				if (charArr[i] == '9') {
					charArr[i] = 'a';
				} else {
					charArr[i] = (char) (charArr[i] + 1);
				}
				break;
			}
		}
		for (i = 0; i < 8; i++) {
			if (charArr[i] == '0') {
				i++;
			} else {
				break;
			}
		}
		return new String(charArr, i, 8 - i);
	}	
    
    /**
	 * 453. 最小移动次数使数组元素相等
	 * 给定一个长度为 n 的非空整数数组，找到让数组所有元素相等的最小移动次数。每次移动可以使 n - 1 个元素增加 1。
	 * 
	 * 示例:
	 * 输入: [1,2,3]
	 * 输出: 3
	 * 解释: 只需要3次移动（注意每次移动会增加两个元素的值）：
	 * [1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]
	 * 
	 * @param nums
	 * @return
	 */
	public int minMoves(int[] nums) {
		int len = nums.length;
		if (len == 0) {
			return 0;
		}
		int min = nums[0];
		int count = 0;
		for (int i = 1; i < len; i++) {
			if (nums[i] < min) {
				count += (min - nums[i]) * i;
				min = nums[i];
			} else {
				count += (nums[i] - min);
			}
		}
		return count;
	}
    
    /**
	 * 448. 找到所有数组中消失的数字
	 * 给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。
	 * 找到所有在 [1, n] 范围之间没有出现在数组中的数字。
	 * 您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
	 * 
	 * 示例:
	 * 输入: [4,3,2,7,8,2,3,1]
	 * 输出: [5,6]
	 * 
	 * @param nums
	 * @return
	 */
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> list = new ArrayList<Integer>();
        int i = 0;
        // 通过一趟遍历，交换，使nums[0...len-1]分别存1...N。
        while (i < nums.length) {
            int num = nums[i];
            if (num == 0 || num == i + 1) {
                i++;
                continue;
            }
            if (nums[num - 1] == num) {
                nums[i] = 0;
                i++;
            } else {
                // 交换 i 和 nums[i]-1 两个位置上的数字
                nums[i] = num ^ nums[num - 1];
                nums[num - 1] = nums[i] ^ nums[num - 1];
                nums[i] = nums[i] ^ nums[num - 1];
            }
        }
        for (int j = 0; j < nums.length; j++) {
            if (nums[j] == 0) {
                list.add(j+1);
            }
        }
        return list;
    
    }  
    
    /**
	 * 796. 旋转字符串
	 * 给定两个字符串, A 和 B。
	 * A 的旋转操作就是将 A 最左边的字符移动到最右边。 例如, 若 A = 'abcde'，在移动一次之后结果就是'bcdea'
	 * 。如果在若干次旋转操作之后，A 能变成B，那么返回True。
	 * 
	 * 示例 1: 
	 * 输入: A = 'abcde', B = 'cdeab' 
	 * 输出: true
	 * 
	 * 示例 2: 
	 * 输入: A = 'abcde', B = 'abced' 
	 * 输出: false 
	 * 
	 * 注意：
	 * A 和 B 长度不超过 100。
	 * 
	 * @param A
	 * @param B
	 * @return
	 */
	public boolean rotateString(String A, String B) {
		if (A.length() != B.length()) {
			return false;
		}
		return (A + A).indexOf(B) > -1;
	}
    
    /**
	 * 788. 旋转数字
	 * 我们称一个数 X 为好数, 如果它的每位数字逐个地被旋转 180 度后，我们仍可以得到一个有效的，且和 X 不同的数。要求每位数字都要被旋转。
	 * 如果一个数的每位数字被旋转以后仍然还是一个数字， 则这个数是有效的。0, 1, 和 8 被旋转后仍然是它们自己；2 和 5 可以互相旋转成对方；6
	 * 和 9 同理，除了这些以外其他的数字旋转以后都不再是有效的数字。
	 * 现在我们有一个正整数 N, 计算从 1 到 N 中有多少个数 X 是好数？
	 * 
	 * 示例: 
	 * 输入: 10 
	 * 输出: 4 
	 * 解释: 在[1, 10]中有四个好数： 2, 5, 6, 9。 
	 * 注意 1 和 10 不是好数, 因为他们在旋转之后不变。 
	 * 
	 * 注意:
	 * N 的取值范围是 [1, 10000]。
	 * 
	 * @param N
	 * @return
	 */
    public int rotatedDigits(int N) {
    	//2,5,6,9个位4个，非首位0、1、8、2,5,6,9
    	//12,15,16,19,8...十位非首位0、1、8、2,5,6,9
    	//首位1、8、2,5,6,9
		// 4 + 6*4 + 6*7*4 + 2*3*3*4
    	int sum = 0;
    	for (int i = 1; i <= N; i++) {
			if (isX(i)) {
				sum++;
			}
		}
		return sum;
    }
    
	private boolean isX(int num) {
		char[] chars = ("" + num).toCharArray();
		int len = chars.length;
		if (len == 1) {
			return chars[0] == '2' || chars[0] == '5' || chars[0] == '6' || chars[0] == '9';
		} else {
			int numX = 0;
			int mul = 1;
			for (int i = len - 1; i >= 0; i--) {
				if (chars[i] == '3' || chars[i] == '4' || chars[i] == '7') {
					return false;
				}
				numX += mul * (rotate(chars[i]) - '0');
				mul *= 10;
			}
			return numX != num;
		}
	}

	private char rotate(char ch) {
		if (ch == '1' || ch == '8' || ch == '0') {
			return ch;
		}
		if (ch == '2') {
			return '5';
		} else if (ch == '5') {
			return '2';
		} else if (ch == '6') {
			return '9';
		} else if (ch == '9') {
			return '6';
		}
		return ch;
	}

	/**
	 * 784. 字母大小写全排列
	 * 
	 * 给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。
	 * 
	 * 示例: 
	 * 输入: S = "a1b2" 
	 * 输出: ["a1b2", "a1B2", "A1b2", "A1B2"]
	 * 
	 * 输入: S = "3z4" 
	 * 输出: ["3z4", "3Z4"]
	 * 
	 * 输入: S = "12345" 
	 * 输出: ["12345"] 
	 * 
	 * 注意：
	 * S 的长度不超过12。 
	 * S 仅由数字和字母组成。
	 * 
	 * @param S
	 * @return
	 */
    public List<String> letterCasePermutation(String S) {
		return letterCasePermutation(S, new StringBuilder());
    }
    
	private List<String> letterCasePermutation(String S, StringBuilder prefix) {
		int len = S.length();
		if (len == 0) {
			return Arrays.asList(prefix.toString());
		}
		char ch = S.charAt(0);
		if (ch >= '0' && ch <= '9') {
			return letterCasePermutation(S.substring(1), prefix.append(ch));
		} else {
			List<String> list = new ArrayList<String>();
			list.addAll(letterCasePermutation(S.substring(1), new StringBuilder(prefix).append(ch)));
			if (ch >= 'A' && ch <= 'Z') {
				list.addAll(letterCasePermutation(S.substring(1), new StringBuilder(prefix).append((char)(ch - 'A' + 'a'))));
			} else if (ch >= 'a' && ch <= 'z') {
				list.addAll(letterCasePermutation(S.substring(1), new StringBuilder(prefix).append((char)(ch - 'a' + 'A'))));
			}
			return list;
		}
	}
    
}
